Posada jednog gusarskog broda je, posle dugog i napornog puta, stigla na ulaz pećine u kojoj se po njihovoj mapi nalazi blago. Pećina je bila neobičnog oblika - na kraju svakog njenog hodnika se nalazilo račvanje puteva, pri čemu je moguće nastaviti hodnikom levo ili hodnikom desno. Nakon n takvih račvanja, svaki od preostalih hodnika vodi do kovčega sa određenim brojem zlatnika.
Kako je gusara bilo mnogo, na svakom račvanju bi se podelili u dve grupe. Jedna grupa bi krenula levo, druga desno, pri čemu bi se dogovorili da se kasnije nađu na račvanju kako bi podelili plen. Svaka od grupa je u nekom trenutku stigla do kovčega sa zlatnicima i ponela ga nazad. Međutim, pošto su gusari pohlepni, svaki put kada bi se grupe srele, ako bi ukupan broj zlatnika koje poseduju bio veći od k, k zlatnika bi zakopali i ostavili u pećini, kako bi se kasnije vratili po njih.
Izračunati koliko zlatnika su gusari izneli iz pećine. Podrazumevati da, kada su se gusari sreli na početnom račvanju, nisu zakopavali zlatnike. Vremenska i prostorna složenost treba da budu O(2n).
Sa standardnog ulaza se učitavaju prirodni brojevi n i k. Nakon toga se učitava broj zlatnika u svakom od 2n kovčega (računati da u kovčegu nema više od k zlatnika).
Na standardni izlaz ispisati broj zlatnika koji su gusari izneli iz pećine.
3 50
45 48 26 22 14 19 11 2358Gusari koji su skrenuli levo, pa levo u zbiru imaju 93 zlatnika, pa zakopavaju 50 i ostaje im 43.
Kada se sastanu sa gusarima koji su skrenuli levo, pa desno, u zbiru imaju 91 zlatnik, pa zakopavaju 50 i ostaje im 41.
Gusari koji su skrenuli desno u zbiru imaju 67 zlatnika, pa zakopavaju 50 i ostaje im 17.
Kada se susretnu na početnom račvanju, gusari ukupno imaju 58 zlatnika, ali ne zakopavaju ništa.